Najkraća ograda
време | меморија | улаз | излаз |
---|---|---|---|
1 s | 1000 Mb | стандардни излаз | стандардни улаз |
U šumi postoji n vrsta stabala. Za svako od m stabala je data njegova vrsta i geografske koordinate. Šumar hoće da ogradi sva stabla jedne vrste žičanom ogradom pravougaonog oblika (gledano odozgo) čije ivice imaju pravac sever-jug i istok-zapad. Kakvu ogradu treba da napravi tako da potroši najmanje žice?
U prvom redu broj vrsta n i broj stabala m, razdvojeni razmakom. U svakom od sledećih m redova opis jednog stabla: x-koordinata, zatim y-koordinata, i na kraju indeks vrste, razdvojeni razmacima.
U prvom redu indeks ograđene vrste. U drugom redu četiri cela broja razdvojena razmacima koja predstavljaju koordinate temena ograde najmanjeg obima koja obuhvata sva stabla te vrste: najpre x i y koordinata donjeg levog temena, zatim x i y koordinata gornjeg desnog temena (I kvadrant). Ako ima više vrsta koje se mogu ograditi ogradom iste dužine, rešenje je ona sa najmanjim indeksom
1 ≤ n ≤ 500, 1 ≤ m ≤ 5000. Koordinate su celi brojevi u zatvorenom intervalu između 0 i 1000. Dva stabla mogu imati iste koordinate. Svaka vrsta mora biti zastupljena bar jednim stablom, dakle m ≥ n.
2 5
3 1 0
5 2 0
4 2 1
0 4 0
6 0 1
1
4 0 6 2
Морате бити улоговани како бисте послали задатак на евалуацију.